#include "MGraph.cpp"

template <typename T, typename TWeight>
void floyed(MGraph<T, TWeight> &graph, TWeight **weight, int **path) {
    int n = graph.get_num_vertex();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            weight[i][j] = i == j ? TWeight() : graph.get_edge(i, j);
            path[i][j] = graph.has_edge(i, j) ? i : -1;
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                TWeight new_weight = weight[i][k] + weight[k][j];
                if (new_weight < weight[i][j]) {
                    weight[i][j] = new_weight;
                    path[i][j] = path[k][j];
                }
            }
        }
    }
}
